
// 数组最大连续项的和 似乎没有用动态规划

var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};

// 若前一个元素大于0 则将当前元素加上前一个元素

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[-2,1,-3,4,-1,2,1,-5,4]

// -2  1 -2 4 3 5 6 1 5

var maxSubArray = function(nums) {
    let len = nums.length;
    // 确定含义： 以nums[i] 结尾的连续子数组最大和
    let dp = []; // 
    // 初始化
    dp[0] = nums[0]
    // 确定公式
    // - 之前大于0 dp[i] = dp[i-1] + nums[i] 之前小于0 nums[i]
    // dp[i]=max{nums[i],dp[i−1]+nums[i]}
    // 确定循环
    for(let i= 1; i< nums.length; i++){
        if(dp[i-1]>0){
            dp[i] = dp[i-1] + nums[i]
        }else {
            dp[i]= nums[i]
        }
    }
    // 可以在上面便利同时求最大值，为了让dp[i] 清晰故而分开
    let max = dp[0]
    for(let i = 1; i< nums.length;i++){
        max = Math.max(res, dp[i])
    }
    return max;

}